package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定括弧的数量，生成所有可能的组合情况
 * 实例： n = 3, 解决方案集是 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
 * <p>
 * 思路：(使用回溯)
 * 构建一个递归方法：
 * -- 递归入参：需要技巧
 * --- str 本次结果
 * --- res  正确的结果集
 * --- left  本次左括号的数量
 * --- right 本次右括号的数量
 * --- n     括弧的数量
 * -- 逻辑（灵魂步骤）：
 * --- 边界条件：left == n && right == n 时，加入结果
 * --- left < n 时（即，左括号的数量 < 括弧的数量），添加 (、left+1，调用backtrack(...
 * --- left > right时（即，左括号的数量 > 右括号的数量），添加 )、right+1，调用backtrack(...
 *
 * @author hanxinghua
 * @create 2024/2/2
 * @since 1.0.0
 */
public class No22GenerateParentheses {


    public static void main(String[] args) {

        System.out.println(method1(3));


    }


    public static List<String> method1(int n) {
        String str = "";
        List<String> res = new ArrayList<>();
        backtrack(str, res, 0, 0, n);
        return res;
    }

    /**
     * 递归方式
     *
     * @param str   本次结果
     * @param res   正确的结果集
     * @param left  本次左括号的数量
     * @param right 本次右括号的数量
     * @param n     括弧的数量
     */
    private static void backtrack(String str, List<String> res, int left, int right, int n) {
        // 边界条件  left == n && right == n 时，加入结果
        if (left == n && right == n) {
            res.add(str);
            return;
        }
        // left < n 时，添加 (
        if (left < n) {
            backtrack(str + "(", res, left + 1, right, n);
        }
        // left > right时，添加 )
        if (left > right) {
            backtrack(str + ")", res, left, right + 1, n);
        }
    }
}
